1. Field of the Invention
The present invention relates generally to content addressable memories, and more particularly to content addressable memories in which certain bits of a tag are defined as "don't care" bits that are presumed to match corresponding bits of an address applied to the memory. The present invention specifically relates to a content addressable memory having memory cells storing don't care states for address translation.
2. Description of the Background Art
Content addressable memories, or CAMs, are commonly employed by the designers of digital electronics to provide a means for storing binary words, and later comparing a specified binary word to the stored binary words. Typical uses for CAMs include pattern matching memories for optical character recognition, and translation look-aside buffers for digital computers that employ "virtual" memory.
A content addressable memory typically has a plurality of storage locations, and each storage location stores a tag and a data word associated with the tag. When the content addressable memory is addressed with a specified address, each tag is compared to the specified address, and when a match occurs, the data word associated with the matching tag is retrieved and asserted on a data output bus from the memory.
In a content addressable memory of a typical optical character recognition system, a tag is stored in the memory for each possible pattern to be recognized as a character. Each data word is a code representing a specific character, and the code associated with each tag is the code representing the character to be recognized from the pattern represented by the tag.
A translation buffer is often used in a digital computer in order to translate "virtual" addresses to "physical" addresses. The "virtual" addresses are the addresses that are used by a computer program. The "physical" addresses are the addresses that are used by the memory of the computer. In a typical translation buffer, each data word contains a number of the most significant bits of a "physical" address, and the tag associated with the data word is an even greater number of the most significant bits of a "virtual" address that translates to the "physical" address. The translation buffer therefore provides a flexible mapping between the "virtual" addresses and the "physical" addresses. The translation buffer, however, usually is not large enough to store translations of all possible virtual addresses. Therefore, when the translation buffer is addressed with a virtual address, it is possible that none of the stored physical addresses will match the virtual address. When such a translation miss occurs, the required translation is fetched from main memory and loaded into the translation buffer.
In a content addressable memory, the comparison of the specified address and the tags can be performed in various ways, depending on the information represented by the stored addresses. In a translation buffer, a match typically requires an exact match of each bit of the specified address to each corresponding bit in a tag. Moreover, the desirability of high-speed access dictates that the comparisons are performed in parallel, so that each memory cell storing a bit of each tag has a dedicated comparator circuit.
The memory cells for a translation buffer typically are static cells, and each cell has a pair of cross-coupled inverters for retaining memory state. The cross-coupled inverters provide "true" and "complement" versions of a stored bit. The logical outputs of the comparator circuits for each storage location are wired in parallel to a "match" line that runs parallel to a row of memory cells for the storage location. The match line is pulled down when any bit of the tag fails to match its corresponding bit of the specified address. The comparator circuit, for example, includes a first pair of NMOS transistors connected in series between the match line and ground, and a second pair of NMOS transistors connected in series between the match line and ground. True and complement versions of the corresponding specified address bit are supplied by respective "true" and "complement" parallel address lines running perpendicular to the match line. The first pair of NMOS transistors have their gates connected to the true output of the storage cell and complement address line, respectively. The second pair of NMOS transistors have their gates connected to the complement output of the storage cell and the true address line, respectively. Such a construction of a static CAM cell is shown, for example, in FIG. 5 of U.S. Pat. No. 3,806,890 issued Apr. 23, 1974.
For pattern matching applications such as optical character recognition, it is desirable for specified bit positions to be masked from the comparison operation, so that a match between the specified address and a tag does not require a match between these don't care bits. The don't care bits could be specified by a mask applied to the content addressable memory together with the specified address. Various uses for such an "ignore mask" are described, for example, in Potter et al., U.S. Pat. No. 5,014,327. Additional flexibility results by storing information associated with each tag to identify whether each bit in each tag should be presumed to match its corresponding bit of the specified address. The use of such internally-stored don't care masks for optical character recognition is described, for example, in Irvin et al., U.S. Pat. No. 3,717,848 issued Feb. 20, 1973.
Dynamic CAM memory cells are known which incorporate comparison logic and internal storage for a don't care state. Such a dynamic CAM memory cell may employ as few as five MOS transistors, as described in Wade et al., U.S. Pat. No. 4,831,585. Each cell includes two storage transistors connected between a match line and respective ones of two bit lines. Stored potentials are applied to the gates of the storage transistors through write transistors which connect respective gates of the storage transistors to respective ones of the two bit lines. A fifth MOS transistor functions as a directional diode connecting the match line to the storage transistors. A don't care state is stored in the cell when both of the storage transistors are off. Otherwise, one of the storage transistors is on, and the other storage transistors is off, in order to encode a tag bit. A don't care state of a specified address bit, corresponding to an externally-applied don't care mask bit, is applied to the cell by asserting both of the two bit lines low. Otherwise, a specified address bit is applied by setting one of the bit lines high, and the other one of the bit lines low. The specified address bit fails to match an encoded tag bit when the "low" bit line is connected to the match line through the "on" storage transistor.